package com.zp.self.module.level_4_算法练习.数学.数学推理;

/**
 * @author By ZengPeng
 */
public class 力扣_149_直线上最多的点数 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_149_直线上最多的点数().maxPoints(new int[][]{{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}}));
    }

    /**
    题目：给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

     示例 1：
     输入：points = [[1,1],[2,2],[3,3]]
     输出：3

     示例 2：
     输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
     输出：4

     分析：【P 💝💝💝💝💝】
       1.数学：x : y 相等的话，就在一条直线上，Map记录这给比值上的点数总数
                但是这个比值不好存啊 ? 我们用 x * y1 ==  x1 * y 来判断吧 ,
                嘶~不对啊 ： y=f x + k 才是直线方程啊， 还有个k要考虑哦
                嘶~又不对啊 ：要两个点才能构成一个直线方程，意味着有n*n条直线啊  300*300 = 90000 个函数
            思考a.两个点构成的函数式怎么表达嘞?
                  不用表达方程，3个点进行判断  (y1 - y2 ) / (x1-x2)  = (y2 - y3 ) / (x2-x3)  --防止除零异常 ，改为乘法
            优化:1.有重复计算的情况A 、B、D 在一条线上时，不用再循环B、D 线上的点了
                  使用二维数组：记录不用循环的下标值  --反而变慢了
                 2.前两节点的计算多次用到，先用变量记录(A[1]-B[1])
            --执行用时：7 ms, 在所有 Java 提交中击败了80.07%的用户

    边界值 & 注意点：
       1.
     **/
    public int maxPoints(int[][] points) {
        int max=1,length = points.length;
        for (int i = 0; i <length; i++) {//线段的第一个点
            for (int j = i+1; j < length; j++) {//线段的第二个点
                int numb = 2;//这条线上的点个数
                int x = (points[i][0]- points[j][0]);
                int y = (points[i][1]- points[j][1]);
                for (int k = j+1; k < length; k++) {//线段的第三个点
                    if(y *(points[k][0]-points[j][0]) == (points[k][1]-points[j][1])*x){
                        numb++;
                    }
                }
                max = Math.max(max,numb);
            }
        }
        return max;
    }
}
